#define _CRT_SECURE_NO_WARNINGS

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 /**
  * Return an array of arrays of size *returnSize.
  * The sizes of the arrays are returned as *returnColumnSizes array.
  * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
  */
typedef struct TreeNode* QueueDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QueueDataType data;
}QNode;

typedef struct Queue
{
    QNode* front;
    QNode* tail;
}Queue;

void QueueInit(Queue* pq)
{
    assert(pq);

    pq->front = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);

    while (pq->front)
    {
        QNode* temp = pq->front->next;
        free(pq->front);
        pq->front = temp;
    }

    free(pq);
}

bool QueueEmpty(Queue* pq)
{
    return pq->front == NULL;
}

void QueuePush(Queue* pq, QueueDataType val)
{
    assert(pq);

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    newNode->data = val;
    newNode->next = NULL;

    if (QueueEmpty(pq))
    {
        pq->front = pq->tail = newNode;
    }
    else
    {
        pq->tail->next = newNode;
        pq->tail = newNode;
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    QNode* temp = pq->front;
    pq->front = pq->front->next;
    free(temp);

    if (pq->front == NULL)
        pq->tail = NULL;
}

QueueDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->front->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);

    int ret = 0;
    QNode* cur = pq->front;
    while (cur)
    {
        ret++;
        cur = cur->next;
    }

    return ret;
}

int TreeHight(struct TreeNode* root)
{
    if (root == NULL)
        return 0;

    return fmax(TreeHight(root->left), TreeHight(root->right)) + 1;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    *returnSize = TreeHight(root);
    printf("%d ", *returnSize);

    if (*returnSize == 0)
        return NULL;

    int** ret = (int**)malloc(sizeof(int*) * (*returnSize));
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));

    Queue* q = (Queue*)malloc(sizeof(Queue));
    QueueInit(q);

    int deep = 0;
    QueuePush(q, root);
    while (!QueueEmpty(q))
    {
        int size = QueueSize(q);
        printf("size = %d\n", size);

        (*returnColumnSizes)[deep] = size;
        ret[deep] = (int*)malloc(sizeof(int) * size);



        int index = 0;
        while (size--)
        {
            struct TreeNode* front = QueueFront(q);
            QueuePop(q);

            ret[deep][index++] = front->val;
            printf("SUCCSEE\n");

            if (front->left)
                QueuePush(q, front->left);
            if (front->right)
                QueuePush(q, front->right);


        }

        deep++;
    }

    QueueDestroy(q);

    return ret;
}